package com.demo.java.OD251_300.OD263;

import java.util.HashSet;

/**
 * @author: luoyong
 * @date: 2025-03-06 9:40
 * @desc:
 */
public class SolveMethod {
    int ans; // 最短路径长度
    HashSet<String> visit; // 记录访问过的坐标
    char[][] arr; // 存储迷宫图
    int endx, endy; // 终点坐标
    int m, n; // 迷宫的行列数

    // 主方法：调用DFS进行路径搜索
    public void help(char[][] arr, int startx, int starty, int endx, int endy, int m, int n) {
        // 如果起点或终点无效，则直接返回
        if (startx == -1 || endx == -1 || starty == -1 || endy == -1) {
            return;
        }

        ans = 999999; // 初始化最短路径为一个非常大的值
        visit = new HashSet<>(); // 初始化访问记录集合
        this.arr = arr;
        this.endx = endx;
        this.endy = endy;
        this.m = m;
        this.n = n;

        // 从起点进行深度优先搜索
        dfs(startx, starty, -1, -1); // 初始方向没有
    }

    // 深度优先搜索方法
    private void dfs(int x, int y, int length, int direction) {
        // 如果到达终点，更新最短路径
        if (x == endx && y == endy) {
            ans = Math.min(length, ans);
            return;
        }

        visit.add(x + "," + y); // 记录当前位置已访问
        int[][] nextarr = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 上下左右四个方向

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int tx = x + nextarr[i][0];
            int ty = y + nextarr[i][1];

            // 判断是否越界、是否为障碍物、是否已访问过
            if (tx < 0 || ty < 0 || tx >= m || ty >= n || arr[tx][ty] == 'X' || visit.contains(tx + "," + ty)) {
                continue;
            }

            // 递归搜索下一个位置，增加路径长度
            dfs(tx, ty, length + 1 + (i != direction ? 1 : 0), i); // 如果改变方向，路径成本加1
        }
    }
}
